1. Field of the Invention
The present invention relates to the efficient implementation of computations expressed in high-level programming languages on multiprocessor computers.
2. The Related Art
Compilers of various designs have been proposed for translating source programs in high level language to target programs in machine code or assembly language for execution by conventional sequential computers. Such compilers have been variously classified as single-pass, multi-pass, load-and-go, debugging, or optimizing--depending on their construction or function. In a typical optimizing compiler, for example, attention is focused on one program section at a time, and any change that improves the speed of execution of one section almost always yields an improvement in overall performance. Since the introduction of supercomputers that achieve high performance through the pipelining of vector operations, much effort has been devoted to so-called vectorizing compilers, compilers that identify sections of code that may be replaced by vector operations. These conventional compiling techniques are inadequate for producing efficient machine code programs for multiprocessor computers generally. The principles of the present invention are illustrated by way of example in reference to a dataflow multiprocessor. To achieve best performance on a multiprocessor, it is necessary to keep each processing element as fully occupied with useful computational work as possible. For this purpose, a global analysis of the source program is necessary.
The present invention introduces implementation techniques based on the global organization of data structure definitions in the source program. Key issues resolved in the invention are the partition of the computation into a time-sequence of phases, and the optimum allocation of code blocks, representing data structure values, to the processing elements and memories of a multiprocessor computer.